package main

import "fmt"

// 旋转数组排序，查找某个数是否在其中
// 1. 找到旋转点 (也是使用二分查找的方式)
// 2. 在旋转分割的序列中使用二分查找找到target
func main() {
	arr := []int{7, 8, 9, 0, 1, 2, 3}
	res := search(arr, 6)
	fmt.Println(res)
}

func search(nums []int, target int) int {
	l, r := 0, len(nums)-1

	// 能否找到分割点是关键
	for l < r {
		mid := l + ((r - l) >> 1)
		fmt.Println(l, r, mid)

		if nums[mid] > nums[r] {
			l = mid + 1
		} else {
			r = mid
		}
	}
	pos := l //最后的pos是left
	fmt.Println(pos, nums[:pos], nums[pos:])

	res := binarysearch(nums[:pos], target)
	if res == -1 {
		res = binarysearch(nums[pos:], target)
		if res != -1 { // 如果找到了要加上原先的pos
			return res + pos
		}
	}
	return res
}

func binarysearch(nums []int, target int) int {
	l, r := 0, len(nums)-1

	for l <= r {
		mid := l + ((r - l) >> 1)
		if target == nums[mid] {
			return mid
		} else if target > nums[mid] { // 在右边
			l = mid + 1
		} else {
			r = mid - 1
		}
	}
	return -1
}
